{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of K-Big Indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kBigIndices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计 K-Big 索引的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>下标从0开始</strong> 的整数数组 <code>nums</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果满足以下条件，我们称下标 <code>i</code> 为 <strong>k-big</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>存在至少 <code>k</code> 个不同的索引 <code>idx1</code> ，满足 <code>idx1 &lt; i</code> 且 <code>nums[idx1] &lt; nums[i]</code> 。</li>\n",
    "\t<li>存在至少 <code>k</code> 个不同的索引 <code>idx2</code> ，满足 <code>idx2 &gt; i</code> 且 <code>nums[idx2] &lt; nums[i]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 k-big 索引的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,6,5,2,3], k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>在nums中只有两个 2-big 的索引:\n",
    "- i = 2 --&gt; 有两个有效的 idx1: 0 和 1。有三个有效的 idx2: 2、3 和 4。\n",
    "- i = 3 --&gt; 有两个有效的 idx1: 0 和 1。有两个有效的 idx2: 3 和 4。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1], k = 3\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>在 nums 中没有 3-big 的索引\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-k-big-indices](https://leetcode.cn/problems/count-the-number-of-k-big-indices/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-k-big-indices](https://leetcode.cn/problems/count-the-number-of-k-big-indices/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6,5,2,3]\\n2', '[1,1,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if 2 * k >= n:\n",
    "            return 0\n",
    "        hp1 = []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(hp1, -nums[i])\n",
    "        kBigLeft = [0] * (n-2*k)\n",
    "        for i in range(k, n-k):\n",
    "            kBigLeft[i-k] = -hp1[0]\n",
    "            heapq.heappush(hp1, -nums[i])\n",
    "            heapq.heappop(hp1)\n",
    "        hp2 = []\n",
    "        kBigRight = [0] * (n-2*k)\n",
    "        for i in range(n-1, n-k-1, -1):\n",
    "            heapq.heappush(hp2, -nums[i])\n",
    "        for i in range(n-k-1, k-1, -1):\n",
    "            kBigRight[i-k] = -hp2[0]\n",
    "            heapq.heappush(hp2, -nums[i])\n",
    "            heapq.heappop(hp2)\n",
    "        result = 0\n",
    "        for i in range(k, n-k):\n",
    "            if nums[i] > kBigLeft[i-k] and nums[i] > kBigRight[i-k]:\n",
    "                result += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0]*(n+1)\n",
    "\n",
    "    def lowbit(self, idx):\n",
    "        return idx & -idx\n",
    "\n",
    "    def update(self, idx, val):\n",
    "        while(idx <= self.n):\n",
    "            self.c[idx] += val\n",
    "            idx = idx + self.lowbit(idx)\n",
    "\n",
    "    def query(self, idx):\n",
    "        ans = 0\n",
    "        while(idx >0):\n",
    "            ans += self.c[idx]\n",
    "            idx = idx - self.lowbit(idx)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        max_num = max(nums)\n",
    "        n = len(nums)\n",
    "\n",
    "        left = BIT(max_num+1)\n",
    "        right = BIT(max_num+1)\n",
    "\n",
    "        for each in nums:\n",
    "            right.update(each, 1)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            right.update(nums[i], -1)\n",
    "            if (right.query(nums[i]-1)>= k and left.query(nums[i]-1)>=k):\n",
    "                ans+=1\n",
    "            left.update(nums[i],1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & (-x)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, x, d):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += d\n",
    "            x += lowbit(x)\n",
    "    \n",
    "    def query(self, x):\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= lowbit(x)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if k * 2 >= n:\n",
    "            return 0\n",
    "\n",
    "        left, right = BIT(n), BIT(n)\n",
    "        for v in nums:\n",
    "            right.update(v, 1)\n",
    "        \n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            right.update(v, -1)\n",
    "            left.update(v, 1)\n",
    "            if left.query(v - 1) >= k and right.query(v - 1) >= k:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & (-x)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, x, d):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += d\n",
    "            x += lowbit(x)\n",
    "    \n",
    "    def query(self, x):\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= lowbit(x)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if k * 2 >= n:\n",
    "            return 0\n",
    "\n",
    "        left, right = BIT(n), BIT(n)\n",
    "        for v in nums:\n",
    "            right.update(v, 1)\n",
    "        \n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            right.update(v, -1)\n",
    "            if left.query(v - 1) >= k and right.query(v - 1) >= k:\n",
    "                ans += 1\n",
    "            left.update(v, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums, k):\n",
    "        cur, res = [], 0\n",
    "        tot = sorted(nums)\n",
    "        for x in nums:\n",
    "            left = bisect.bisect_left(cur, x)\n",
    "            right = bisect.bisect_left(tot, x)\n",
    "            if left >= k and right - left >= k:\n",
    "                res += 1\n",
    "            bisect.insort(cur, x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        sl = SortedList()\n",
    "        arr = sorted(nums)\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            a = sl.bisect_left(x)\n",
    "            b = bisect_left(arr, x)\n",
    "            if a >= k and b - a >= k:\n",
    "                ans += 1\n",
    "            sl.add(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        k_big_count = 0\n",
    "        left_sorted = SortedList()\n",
    "        right_sorted = SortedList(nums)\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            # 移除当前元素，因为我们不包括自己进行比较\n",
    "            right_sorted.remove(num)\n",
    "\n",
    "            # 计算小于当前元素的数量\n",
    "            left_count = left_sorted.bisect_left(num)\n",
    "            right_count = right_sorted.bisect_left(num)\n",
    "\n",
    "            if left_count >= k and right_count >= k:\n",
    "                k_big_count += 1\n",
    "\n",
    "            # 将当前元素添加到左侧有序列表\n",
    "            left_sorted.add(num)\n",
    "\n",
    "        return k_big_count\n",
    "\n",
    "# 测试用例\n",
    "sol = Solution()\n",
    "print(sol.kBigIndices([20,9,15,15,7,14,3,6,7,5,19,16,13,17,2,5,8,4,11,12], 9))  # 输出应为 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        sl = SortedList()\n",
    "        arr = sorted(nums)\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            a = sl.bisect_left(x)\n",
    "            b = bisect_left(arr, x)\n",
    "            if a >= k and b - a >= k:\n",
    "                ans += 1\n",
    "            sl.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        a = SortedList()\n",
    "        left = [0] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            left[i] = a.bisect_left(nums[i])\n",
    "            a.add(nums[i])\n",
    "        res = 0\n",
    "        a.clear()\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            ri = a.bisect_left(nums[i])\n",
    "            a.add(nums[i])\n",
    "            if ri >= k and left[i] >= k:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kBigIndices(self, a: List[int], k: int) -> int:\n",
    "        st = SortedList([])\n",
    "        end = SortedList(a[1:])\n",
    "        ans = 0\n",
    "        for j in range(len(a))[1:]:\n",
    "            end.remove(a[j])\n",
    "            i = end.bisect_left(a[j])\n",
    "            st.add(a[j-1])\n",
    "            l = st.bisect_left(a[j])\n",
    "            if (i>=k) and (l>=k):\n",
    "                ans += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        leftarr = []\n",
    "        idx1arr = []\n",
    "        for num in nums:\n",
    "            idx1arr.append(bisect_left(leftarr,num))\n",
    "            insort(leftarr,num) \n",
    "            #print(leftarr, idx1arr)\n",
    "\n",
    "        rightarr = []\n",
    "        idx2arr = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            idx2arr.append(bisect_left(rightarr,nums[i]))\n",
    "            insort(rightarr,nums[i])\n",
    "            #print(rightarr, idx2arr)\n",
    "        idx2arr = idx2arr[::-1]\n",
    "        \n",
    "        return sum(1 for i in range(n) if idx1arr[i]>=k and idx2arr[i]>=k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        sort_list = []\n",
    "        left_list = []\n",
    "        for i in range(len(nums)):\n",
    "            insert_pos = bisect.bisect_left(sort_list, nums[i])\n",
    "            left_list.append(insert_pos)\n",
    "            sort_list.insert(insert_pos, nums[i])\n",
    "        \n",
    "        sort_list = []\n",
    "        right_list = []\n",
    "        for i in range(len(nums)):\n",
    "            insert_pos = bisect.bisect_left(sort_list, nums[len(nums)-i-1])\n",
    "            right_list.append(insert_pos)\n",
    "            sort_list.insert(insert_pos,nums[len(nums)-i-1])\n",
    "        right_list = list(reversed(right_list))\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if left_list[i] >= k and right_list[i] >= k:\n",
    "                res +=1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "\n",
    "    def update(self, x):\n",
    "        while x <= self.n:\n",
    "            self.a[x] += 1\n",
    "            x += BIT.lowbit(x)\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x:\n",
    "            res += self.a[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        bit = BIT(n := len(nums))\n",
    "        ans, sm = 0, 0\n",
    "        c = defaultdict(list)\n",
    "        for i, x in enumerate(nums): c[x].append(i + 1)\n",
    "        for x in sorted(c):\n",
    "            for i in c[x]:\n",
    "                a = bit.query(i)\n",
    "                ans += int(sm - k >= a >= k)\n",
    "            for i in c[x]:\n",
    "                bit.update(i)\n",
    "            sm += len(c[x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.a = [0] * (n + 1)\n",
    "\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "\n",
    "    def update(self, x):\n",
    "        while x <= self.n:\n",
    "            self.a[x] += 1\n",
    "            x += BIT.lowbit(x)\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x:\n",
    "            res += self.a[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        bit = BIT(n := len(nums))\n",
    "        ans, sm = 0, 0\n",
    "        c = defaultdict(list)\n",
    "        for i, x in enumerate(nums): c[x].append(i + 1)\n",
    "        for x in sorted(c):\n",
    "            for i in c[x]:\n",
    "                a = bit.query(i)\n",
    "                ans += int(sm - k >= a >= k)\n",
    "            for i in c[x]:\n",
    "                bit.update(i)\n",
    "            sm += len(c[x])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kBigIndices(self, nums: List[int], k: int) -> int:\n",
    "        test = []\n",
    "        left = set()\n",
    "        right = set()\n",
    "        for i in range(len(nums)):\n",
    "            l = bisect.bisect_left(test, nums[i])\n",
    "            if l >= k:\n",
    "                left.add(i)\n",
    "            test.insert(l, nums[i])\n",
    "        test = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            l = bisect.bisect_left(test, nums[i])\n",
    "            if l >= k:\n",
    "                right.add(i)\n",
    "            test.insert(l, nums[i])\n",
    "        return len(left & right)\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
